package com.example.algorithm;

import java.nio.charset.StandardCharsets;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * BFS获取每个零售店到最近仓库最短距离，并输出距离之和
 *
 * @DATE 2024/6/25
 **/
public class BFS3 {

    // 0仓库，-1障碍，1零售店
    // 无法到达仓库的零售店不参与计算
    // 没有零售店或者没有仓库，则返回0
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int rows = cin.nextInt();
        int cols = cin.nextInt();
        int[][] grids = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grids[i][j] = cin.nextInt();
            }
        }
        cin.close();
        System.out.println(nearestWareHouse(grids));
    }

    private static int nearestWareHouse(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        // 仓库节点坐标
        Queue<int[]> visitQueue = new LinkedList<>();
        // 记录已访问和未访问标记
        boolean[][] visited = new boolean[rows][cols];
        // 遍历grid，把所有仓库节点坐标放入bfs队列
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    // 如果是仓库节点，入队，设置visited[i][j] = true，设置未访问过
                    visitQueue.add(new int[]{i, j});
                    visited[i][j] = false;
                } else if (grid[i][j] == -1) {
                    // 障碍物，设置未访问过
                    visited[i][j] = false;
                } else {
                    // 仓库，设置已访问过
                    visited[i][j] = true;
                }
            }
        }
        // 初始化步长为1，此时队列中为仓库，以仓库为中心，以1为步长，向四周扩散
        // 将已遍历的节点设置为-1
        int step = 1;
        int result = 0;
        while (!visitQueue.isEmpty()) {
            int qcount = visitQueue.size();
            for (int i = 0; i < qcount; i++) {
                // 出队列，向该节点四周扩散
                // poll从队列中移除并返回头部元素
                int[] temp = visitQueue.poll();
                int x = temp[0];
                int y = temp[1];
                // 右边
                if (x + 1 < rows && visited[x + 1][y]) {
                    result += step;
                    visited[x + 1][y] = false;
                    visitQueue.add(new int[]{x + 1, y});
                }
                // 左边
                if (x - 1 >= 0 && visited[x - 1][y]) {
                    result += step;
                    visited[x - 1][y] = false;
                    visitQueue.add(new int[]{x - 1, y});
                }
                // 上面
                if (y - 1 >= 0 && visited[x][y - 1]) {
                    result += step;
                    visited[x][y - 1] = false;
                    visitQueue.add(new int[]{x, y - 1});
                }
                // 下面
                if (y + 1 < cols && visited[x][y + 1]) {
                    result += step;
                    visited[x][y + 1] = false;
                    visitQueue.add(new int[]{x, y + 1});
                }
            }
            step++;
        }
        return result;
    }
}
